import java.util.Arrays;
import java.util.Stack;

public class test {
    //直接插入法
    public static void insertSort(int[] array){
        //时间复杂度
        //O(N*2)最坏情况下--逆序
        //O（N）最好情况下--有序
        //插入排序，数据越有序的时候越快！
        //空间复杂度O（1）
        //稳定性：稳定的排序
        for (int i = 1; i < array.length;i++){
            //从第二个数插入开始排序
            int tmp =array[i];
            int j = i-1;
            for (j = i-1; j >=0;j--){
                if (array[j] > tmp){
                    array[j+1] = array[j];
                }else {
                    //array[j+1] = tmp;//可以省略掉
                    break;
                }
            }
            array[j+1] =tmp;
        }
    }

    public static void main1(String[] args) {
        int[] array = {1,5,2,9,3,6};
        //insertSort(array);//
        //shellSort(array);
        //selectSort2(array);
        //heapSort(array);
        //quickSort2(array);
        mergeSort(array);
        System.out.println(Arrays.toString(array));
    }

    public static void shellSort(int array[]){
        int gap = array.length;
        while (gap >1){
            gap/=2;
            shell(array,gap);
        }
        //shell(array,1)//没必要，gap一定会走一次1
    }

    //每组自己插入排序
    private static void shell(int[] array,int gap){
        for (int i = gap; i < array.length;i++){
            //从第二个数插入开始排序
            int tmp =array[i];
            int j = i-gap;
            for (; j >=0;j-=gap){
                if (array[j] > tmp){
                    array[j+gap] = array[j];
                }else {
                    //array[j+gap] = tmp;//可以省略掉
                    break;
                }
            }
            array[j+gap] =tmp;
        }
    }

//选择排序
    public static void selectSort1(int[] array){
        for (int i = 0;i< array.length;i++){
            int minIndx = i;
            for (int j = i+1;j < array.length;j++){
                if (array[j] < array[minIndx]){
                    minIndx = j;
                }
            }
            swap(array,minIndx,i);
        }
    }

    public static void swap(int[] array,int i,int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    public static void selectSort2(int[] array){
        int left = 0;
        int right = array.length-1;
        while (left<right){
            int minIndex = left;
            int maxIndex = left;//假设最大值最小值都是left
            for (int i = left +1; i<=right ;i++){
                if (array[i] < array[minIndex]){
                    minIndex = i;
                }
                if (array[i]>array[maxIndex]){
                    maxIndex = i;
                }
            }
            swap(array,minIndex,left);
            //最大值正好和最小值进行了交换
            if (maxIndex == left){
                maxIndex = minIndex;
            }
            swap(array,maxIndex,right);
            left++;
            right--;
        }
    }


    //借堆排序
    public static void heapSort(int[] array){
        createBigHeap(array);
        int end = array.length-1;
        while (end > 0){
            swap(array,end,0);
            siftDown(array,0,end);
            end--;
        }
    }

    private static void createBigHeap(int[] array){
        for (int i = (array.length-1-1)/2 ; i >=0;i--){
            siftDown(array,i,array.length);
        }
    }

    private static void siftDown(int[] array,int parent,int len){
        //已知孩子节点去求孩子节点
        int child = parent*2 + 1;
        while (child < len){
            if (child+1 < len && array[child] < array[child+1]){
                child++;
            }
            if (array[child] > array[parent]){
                swap(array,child,parent);
                parent = child;
                child = 2*parent + 1;
            }else {
                break;
            }
        }
    }

    //冒泡排序
    //一趟下来最大的元素排在最后面
    public static void bubbleSort(int[] array){
        for (int i = 0; i < array.length-1;i++){
            boolean flg = false;
            for (int j = 0; j < array.length-1-i;j++){
                if (array[i] > array[j+1]){
                    swap(array,j,j+1);
                    flg = true;
                }
            }
            if (!flg){
                break;
            }
        }
    }


    //快速排序
    //时间复杂度N*logn[最好情况下]
    //n*2【最坏情况下】
    public static void quickSort(int[] array){
        quick(array,0,array.length-1);
    }


    //三数取中，返回下标，进行交换
    private static int threeNum(int[] array,int left,int right){
        int mid = (left+right)/2;
        if (array[left] < array[right]){
            if (array[mid]<array[left]){
                return left;
            }else if (array[mid] > array[right]){
                return right;
            }else {
                return mid;
            }
        }else {
            if (array[mid]<array[right]) {
                return right;
            }else if (array[mid] > array[left]){
                return left;
            }else {
                return mid;
            }
        }
    }


    private static void insertSort2(int[] array,int left,int right){
        //时间复杂度
        //O(N*2)最坏情况下--逆序
        //O（N）最好情况下--有序
        //插入排序，数据越有序的时候越快！
        //空间复杂度O（1）
        //稳定性：稳定的排序
        for (int i = left + 1; i <= right ;i++){
            //从第二个数插入开始排序
            int tmp =array[i];
            int j = i-1;
            for (j = i-1; j >= left;j--){
                if (array[j] > tmp){
                    array[j+1] = array[j];
                }else {
                    //array[j+1] = tmp;//可以省略掉
                    break;
                }
            }
            array[j+1] =tmp;
        }
    }


    private static void quick(int[] array,int start,int end){
        if (start >= end){
            return;
        }
        //System.out.println("start: "+start);
        //System.out.println("end: "+end);
        if (end - start + 1 <= 20) {
            //直接插入排序
            insertSort2(array, start, end);
        }

        //三数取中
        int mid = threeNum(array,start,end);
        //交换
        swap(array,mid,start);

        int pivot = parttion2(array,start,end);

        quick(array,start,pivot-1);//左树

        quick(array,pivot+1,end);//右树
    }

    //Hoare法
    private static int parttion(int[] array,int left,int right){
        int i = left;//记录这个位置
        int tmp = array[left];
        while (left<right){
            while (left<right && array[right] >= tmp){
                right--;//right找比小的数据
            }
            //todo：先检查前面的会不会有问题
            while (left<right && array[left] <= tmp){
               left++;
            }
            swap(array,left,right);
        }
        swap(array,left,i);
        return left;//left与right相遇
    }

    //挖坑法
    private static int parttion2(int[] array,int left,int right){
        int tmp = array[left];
        while (left<right){
            while (left<right && array[right] >= tmp){
                right--;//right找比小的数据
            }

            array[left] = array[right];
            //todo：先检查前面的会不会有问题
            while (left<right && array[left] <= tmp){
                left++;
            }
            array[right] = array[left];
        }
        array[left] = tmp;
        return left;//left与right相遇
    }
    //非递归实现排序
    public static void quickSort2(int[] array){
        Stack<Integer> stack = new Stack<>();
        int start = 0;
        int end = array.length -1;

        if (end - start + 1 <= 20) {
            //直接插入排序
            insertSort2(array, start, end);
            return;
        }

        //三数取中
        int mid = threeNum(array,start,end);
        //交换
        swap(array,mid,start);

        int pivot = parttion(array,start,end);
        if (pivot > start+1){
            stack.push(start);
            stack.push(pivot-1);
        }

        if (pivot<end-1){
            stack.push(pivot+1);
            stack.push(end);
        }

        while (!stack.empty()){
            end = stack.pop();
            start = stack.pop();

            if (end - start + 1 <= 20) {
                //直接插入排序
                insertSort2(array, start, end);
                //return;  不能return，否则只有一部分
            }else {
                //三数取中
                mid = threeNum(array, start, end);
                //交换
                swap(array, mid, start);

                pivot = parttion(array, start, end);
                if (pivot > start + 1) {
                    stack.push(start);
                    stack.push(pivot - 1);
                }

                if (pivot < end - 1) {
                    stack.push(pivot + 1);
                    stack.push(end);
                }
            }
        }
    }


    private static void merge(int[] array,int left,int mid,int right){
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;
        //两个段里面都有数据
        int[] tmpArr = new int[right - left +1];
        int k = 0;//tmpArr数组的xiab
        while (s1 <= e1 && s2 <= e2){
            if (array[s1] <= array[s2]){
                tmpArr[k++] = array[s1++];
            }else {
                tmpArr[k] = array[s2];
                s2 ++;
                k++;
            }
        }
        //已经有一段走完
        while (s1 <= e1){
            tmpArr[k++] = array[s1++];
        }

        while (s2 <= e2){
            tmpArr[k++] = array[s2++];
        }
        //把tmp数组拷回原来的数组
        //写法一 错误；右边是4，5，6，7...，
       /* for (int i = 0 ; i < k;i++){
            array[i] = tmpArr[i];
        }*/

        //真确
        for (int i = 0 ; i < k;i++){
            array[i + left] = tmpArr[i];
        }
    }

    private static void mergeSortFunc(int[] array,int left,int right){
        if (left >= right){//没有左树或者右树，奇或偶
            return;
        }

        int mid = (left + right)/2;
        mergeSortFunc(array,left,mid);
        mergeSortFunc(array,mid+1,right);

        merge(array,left,mid,right);//合并
    }
    public static void mergeSort(int[] array){
        mergeSortFunc(array,0,array.length-1);
    }

    //非递归写法
    public static void mergeSort2(int[] array){
        int gap = 1;
        while (gap < array.length){

            for (int i = 0; i <array.length; i = i + gap*2){//一组是两个，那么两个是四个
                int left = i;
                int mid = left + gap -1;
                int right = mid + gap;
                //mid right有可能会越界

                if (mid >= array.length){
                    mid = array.length -1;
                }
                if (right >= array.length){
                    right = array.length -1;
                }
                merge(array,left,mid,right);
            }

            gap *= 2;
        }

    }


    public static void countArray(int[] array){
        int maxVal = array[0];
        int minVal = array[0];
        //1.遍历数组，找最大最小值O(N)
        for (int i = 1; i < array.length; i++){
            if (array[i] < minVal){
                minVal = array[i];
            }
            if (array[i] > maxVal){
                maxVal = array[i];
            }
        }
        //2.确定计数数组的大小O（n）
        int range = maxVal - minVal +1;
        int[] count = new int[range];
        //3.再次遍历原来的数组，把原来的数据和计数数组下标对应
        for (int i = 0; i < array.length; i++ ){
            int val = array[i];
            count[val - minVal]++;//这里开始计数
        }
        //4.上述循环走完，计数数组已经存好了对应关系，遍历计数数组 O(范围+n)
        int index = 0;//记录重新写回array数组的下标
        for (int i = 0; i < count.length; i++){
            int val = count[i];
            while (val != 0){
                array[index] = i + minVal;
                val --;
                index++;
            }
        }
    }

    public static void main(String[] args) {
        int[] array = {9,5,3,1,2,4,6,8,5,6,4,3,4,5};
        countArray(array);
        System.out.println(Arrays.toString(array));
    }





}
